package com.sheng.leetcode.year2022.month07.day14;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/07/14
 *
 * 745. 前缀和后缀搜索
 *
 * 设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
 * 实现 WordFilter 类：
 * WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
 * f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。
 * 如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
 *
 * 示例：
 *
 * 输入
 * ["WordFilter", "f"]
 * [[["apple"]], ["a", "e"]]
 * 输出
 * [null, 0]
 * 解释
 * WordFilter wordFilter = new WordFilter(["apple"]);
 * wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。
 *  
 * 提示：
 *
 * 1 <= words.length <= 104
 * 1 <= words[i].length <= 7
 * 1 <= pref.length, suff.length <= 7
 * words[i]、pref 和 suff 仅由小写英文字母组成
 * 最多对函数 f 执行 104 次调用
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/prefix-and-suffix-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0745 {

    @Test
    public void test01() {
//        String[] words = {"apple"};
//        String[] words = {"abbba","abba"};
        String[] words = {"c","i","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","i","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","i","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","i","i","c","c","c","c","i","c","i","i","i","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","i","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","i","c","c","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","i","c","i","c","c","c","c","c","i","i","c","i","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","i","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","i","c","c","i","c","i","i","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","i","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","i","c","c","c","i","c","c","c","c","c","c","c","c","i","i","c","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","i","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","i","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","i","i","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","i","i","c","c","c","c","c","c","c","i","i","c","c","c","c","c","i","c","i","i","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","i","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","i","i","c","i","c","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","c","c","i","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","c","c","c","i","c","c","c","i","c","c","c","c","c","i","c","c","i","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","i","i","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","i","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","i","i","c","c","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","i","c","c","c","c","c","c","c","c","c","i","c","c","c","c","i","c","c","c","i","c","c","c","c","c","c","c","c","i","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","c","c","i","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","c","i","i","c","c","c","c","c","i","i","c","i","c","c","c","c","c","c","c","c","c","c","c","i","i","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","c","i","c","c","c","i","c","c","c","c","c","i","c","i","c","c","c","c","i","c","i","c","c","c","c","c","c","i","c","c","c","c","c","c"};
        WordFilter obj = new WordFilter(words);
        System.out.println(obj.f("c", "c"));
    }

}
class WordFilter {

    String[] strs;
    Map<String, List<Integer>> preMap;
    Map<String, List<Integer>> sufMap;

    public WordFilter(String[] words) {
        strs = words;
        preMap = new HashMap<>();
        sufMap = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            //缓存该单词的所有前缀
            for (int j = 1; j <= strs[i].length(); j++) {
                //判断一个map中是否存在这个key，如果存在则处理value的数据，如果不存在，则创建一个满足value要求的数据结构放到value中
                preMap.computeIfAbsent(strs[i].substring(0, i), key -> new ArrayList<Integer>()).add(i);
//                if (preMap.containsKey(strs[i].substring(0, j))) {
//                    preMap.get(strs[i].substring(0, j)).add(i);
//                } else {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i);
//                    preMap.put(strs[i].substring(0, j), list);
//                }
            }
            //缓存该单词的所有后缀
            for (int j = 0; j < strs[i].length(); j++) {
                preMap.computeIfAbsent(strs[i].substring(j), key -> new ArrayList<Integer>()).add(i);
//                if (sufMap.containsKey(strs[i].substring(j))) {
//                    sufMap.get(strs[i].substring(j)).add(i);
//                } else {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i);
//                    sufMap.put(strs[i].substring(j), list);
//                }
            }
        }
    }

    public int f(String pref, String suff) {
        //preList：pref前缀对应的所有单词的index
        List<Integer> preList = preMap.get(pref);
        //sufList：suff后缀对应的所有单词的index
        List<Integer> sufList = sufMap.get(suff);
        //前缀或后缀不存在对应的单词时
        if (preList == null || sufList == null) {
            return -1;
        }
        //从后往前计算
        int preIndex = preList.size() - 1;
        int sufIndex = sufList.size() - 1;
        while (preIndex >= 0 && sufIndex >= 0) {
            if (preList.get(preIndex).equals(sufList.get(sufIndex))) {
                //索引相同，代表找到了同一个单词，由于是从后往前找，该单词最大
                return preList.get(preIndex);
            } else if (preList.get(preIndex) > sufList.get(sufIndex)) {
                //preIndex前缀代表的单词的索引大于后缀对应的索引，前缀继续往前找
                preIndex--;
            } else {
                //sufIndex后缀代表的单词的索引大于前缀对应的索引，后缀继续往前找
                sufIndex--;
            }
        }
        //没有找到前后缀对应的单词，返回-1
        return -1;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */
